package Sort_06;

/*
 * @Author 罗
 * @date 2020/3/17 - 9:15 下午
 *
 */

import org.junit.Test;

import java.util.Arrays;

public class QuickSort_06 {

    @Test
    public void test(){
        int[] array = {1,6,5,2,3,5};
        quickSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }



    /**
     * 老师
     * @param array
     * @param left
     * @param right
     */
    public static void quickSort(int[] array,int left,int right){
        int leftScript = left;
        int rightScript= right;

        int temp;
        /*
        * pivot 中轴
        * */
        int pivot = array[ (left + right) / 2 ];
        /*
        * 左边的索引 <  右边的索引
        * 比pivot小的值放在左边
        * 比pivot大的值放在右边
        *   如果选择首或者尾作为中轴，每次交换都需要把中轴从最左端或者最右端移动到 交点
        * */
        while(leftScript < rightScript){
            /*
            * 在左边一直寻找一个比中轴大于等于的数
            * 找到才跳出循环
            *
            * 当array[leftScript] < pivot 不成立
            * (即array[leftScript] >= pivot)才跳出循环
            *   不要在while中加等号
            *   这里已经相当于，最坏的情况下找到pivot本身就退出了
            * */
            while(array[leftScript] < pivot){
                leftScript++;
            }
            /*
            * 在右边一直寻找一个比中轴小于等于的数
            * 找到才跳出循环
            * */
            while(array[rightScript] > pivot){
                rightScript--;
            }
            /*
            * 如果成立，说明pivot左右两边的值已经完全是
            *   pivot左边的值已经全部小于pivot
            *   pivot右边的值已经全部大于pivot
            * 不可能出现leftScript > rightScript
            * */
            if(leftScript == rightScript){
                break;
            }
            /*
            * 进行交换操作
            * */
            temp = array[leftScript];
            array[leftScript] = array[rightScript];
            array[rightScript] = temp;
            /*
            * 交换完成之后
            * 如果array[leftScript] == pivot
            * 防止下一次循环的时候（本方法的最外层循环，即while(leftScript < rightScript)），
            * 中的while(array[leftScript] < pivot)，条件永远不会满足
            *   直接跳出，而不进入循环去寻找下一个在pivot左边却比pivot大的值
            *   leftScript指针永远指向左边与pivot值相等的元素下标
            *   如果此时在pivot右边找到了小于或者等于pivot的值，则这个值将和leftScript指向的值相交换
            *   这时，while(array[leftScript] < pivot)有可能满足条件（从pivot右边交换过来的值比pivot小的时候）
            *   leftScript指针就会后移，如果在leftScript和pivot之间没有其他元素的情况下
            *   leftScript会指向pivot本身，如果此时rightScript指向的值不满足while(array[rightScript] > pivot)
            *   即array[rightScript] <= pivot的时候，主要是==的情况，
            *   这个情况出现的话,array[rightScript] = pivot，array[leftScript] = pivot，两者在交换操作的时候，一直互相交换
            *   将会造成无限死循环
            *  比如：1,5,5,6,3,2
            *
            * 主要作用:当遇到array={1,3,5,2,5,6}，pivot = 5，leftScript=2,rightScript=4时
            *       while(array[leftScript] < pivot)不会移动leftScript指针
            *       while(array[rightScript] > pivot)不会移动rightScript指针
            *       本方法的最外侧while循环while(leftScript < rightScript)只会把leftScript对应的下标元素和
            *               rightScript对应的下标元素相交换，无限交换，死循环
            *       经过这个方法之后，rightScript = 3，跳出了这个死循环
            * 次要作用：平时的话，会代替while(array[rightScript] > pivot)进行移动元素下标，判断的话还是交给while循环的条件判断
            *       没有负面影响
            * 次要作用：当只剩两个元素的时候，能够让两个元素指针leftScript,rightScript同时指向同一个元素
            *       从而结束最外层while循环
            * */
            if(array[leftScript] == pivot){
                /*
                 * 前移
                 */
                rightScript--;
            }
            /*
            *
            * 当遇到死循环leftScript和rightScript对应下标一直在交换时
            * 在同一次最外层while循环中，若if(array[leftScript] == pivot)执行了
            * 则本次判断if(array[rightScript] == pivot)一般不会执行，因为rightScript已经被if(array[leftScript] == pivot)给减一了
            * 单如果if(array[leftScript] == pivot)解死循环失败的话，array={1,3,5,5,5,6}，这个判断再来解死循环
            * */
            if(array[rightScript] == pivot){
                /*
                 * 后移
                 */
                leftScript++;
            }
        }
        /*
        * 当最外层while结束之后leftScript和rightScript都指向了pivot
        * 这时，需要以pivot为基准，为pivot以左的递归指定上边界
        *                       为pivot以右的递归指定下边界
        * */
        if(leftScript == rightScript){
            /*
            * 如果成立，必须进行，否则栈溢出错误
            * 为pivot以左的递归指定上边界
            * */
            leftScript++;
            /*
            * 为pivot以右的递归指定下边界
            * */
            rightScript--;
        }
        /**
         * 错误写法，因为到这里，可能 leftScript > rightScript
         * if(leftScript == rightScript){
            leftScript--;
            rightScript++;
         * 再结合这个错误，会导致，下面两个递归有交叉的排序部分，最终的排序会有错误
         if(left < leftScript){
            quickSort(array,left,leftScript);
         }
         if(rightScript < right){
         quickSort(array,rightScript,right);
         }
        }*/
        /*
        * 把pivot左边的元素进行递归
        * 向左递归
        * 当递归元素个数大于2个时，进行递归
        * */
        if(left < rightScript){

            quickSort(array,left,rightScript);
        }
        /*
         * 把pivot右边的元素进行递归
         * 向右递归
         * 当递归元素个数大于2个时，进行递归
         * */
        if(right > leftScript){

            quickSort(array,leftScript,right);
        }
    }

}
